// run: $exec < bfdiff.in
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <complex>
#include <cassert>
// #pragma comment(linker,"/STACK:102400000,102400000")
using namespace std;
#define LL long long
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define MAXN 100005
template <typename T> inline void checkMax(T &a, T b) {a = a>b?a:b;}
template <typename T> inline void checkMin(T &a, T b) {a = a<b?a:b;}
typedef pair<int, int> PII;
typedef vector<int> vi;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int INF = 0x3fffffff;
int T, N, M, head[MAXN], cnt;

int ans[MAXN], dis[MAXN];

bool vis[MAXN];

struct Edge {
	int v, next, id;
} p[MAXN << 1];

void init() {
	fill(head, head + MAXN, -1);
	memset(p, 0, sizeof(p));
	memset(ans, 0, sizeof(ans));
	cnt = 0;
}

void addEdge(int u, int v, int id) {
	p[cnt].v = v;
	p[cnt].next = head[u];
	p[cnt].id = id;
	head[u] = cnt ++;
}

struct Node {
	int to, from, id;

	Node() {}

	Node(int to, int from, int id) : to(to), from(from), id(id) {}

	bool operator < (const Node &next) const {
		return to > next.to;
	}
};

struct Node1 {
	int to, from, id;

	Node1() {}

	Node1(int to, int from, int id) : to(to), from(from), id(id) {}

	bool operator < (const Node1 &next) const {
		return to < next.to;
	}
};

void gao2(vector<Node> &vec, int Peak) {
	priority_queue<Node1> Q;
	for (int i = 0; i < vec.size(); i ++) {
		Q.push(Node1(vec[i].to, vec[i].from, vec[i].id));
		if (vec[i].from <= Peak) {
			dis[N] = min(dis[N], dis[vec[i].from] + 1);
		}
	}
	int pre = N;
	while (!Q.empty()) {
		Node1 node = Q.top();
		Q.pop();
		int u = node.to, from = node.from, id = node.id;
		if (u < N) {
			dis[u] = dis[u + 1] + 1;
		}
		if (from <= Peak) {
			if (dis[from] > dis[u]) {
				ans[id] = 0;
			} else {
				ans[id] = dis[u] - dis[from];
			}
		} else {
			if (u > from) {
				continue;
			}
			ans[id] = dis[u] - dis[from];
		}
		if (vis[u]) continue;
		for (int i = head[u]; i != -1; i = p[i].next) {
			int v = p[i].v, id = p[i].id;
			Q.push(Node1(v, u, id));
		}
		vis[u] = true;
		pre = u;
	}
}


void gao() {
	fill(dis, dis + MAXN, INF);
	memset(vis, 0, sizeof(vis));
	priority_queue < Node > Q;
	Q.push(Node(1, 1, 0));
	dis[1] = 0;
	int pre = 1;
	while (!Q.empty()) {
		Node node = Q.top();
		int u = node.to, from = node.from, id = node.id;
		if (pre + 1 < u) break;
		Q.pop();
		if (u < from) continue;
		if (u > 1) {
			dis[u] = dis[u - 1] + 1;
		}
		ans[id] = dis[u] - dis[from];
		if (vis[u]) continue;
		for (int i = head[u]; i != -1; i = p[i].next) {
			int v = p[i].v, id = p[i].id;
			Q.push(Node(v, u, id));
		}
		vis[u] = true;
		pre = u;
	}
	vector<Node> vec;
	while (!Q.empty()) {
		Node node = Q.top();
		Q.pop();
		vec.push_back(node);
	}
	int Peak = pre;
	if (Peak == N) {
		return ;
	} else {
		gao2(vec, Peak);
	}
}

void work() {
	init();
	scanf("%d %d", &N, &M);
	fill(ans, ans + MAXN, N);
	for (int i = 1; i <= M; i ++) {
		int u, v;
		scanf("%d %d", &u, &v);
		addEdge(u, v, i);
	}
	gao();
	for (int i = 1; i <= M; i ++) {
		printf("%d\n", ans[i] == 0 ? N : ans[i]);
	}
}
int main() {
#ifdef __SKT__
	freopen("in", "r", stdin);
#endif
	scanf("%d", &T);
	while (T --) {
		work();
	}
	return 0;
}
